package com.itheima.leetcode.od.b.graph;

import java.util.Arrays;

/**
 * <h1>最大岛屿体积</h1>
 * 给你一个由 大于0的数（陆地）和 0（水）组成的的二维网格，请你计算网格中最大岛屿的体积。陆地的数表示所在岛屿的体积。
 * <p>
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * <p>
 * 此外，你可以假设该网格的四条边均被水包围。
 * <p>
 * 输入描述
 * <p>
 * 第一行是二维网格的宽和高。
 * 后面几行是二维网格。
 * <p>
 * 输出描述
 * <p>
 * 输出岛屿的最大体积。
 * <p>
 * 样例
 * <p>
 * 输入
 * <p>
 * 5 5
 * <p>
 * 0 1 1 0 0
 * <p>
 * 0 1 1 0 0
 * <p>
 * 0 0 0 0 0
 * <p>
 * 0 0 1 2 3
 * <p>
 * 0 0 1 3 9
 * <p>
 * 输出
 * <p>
 * 19
 */
public class DFSMaximumIslandVolume {
    public static void main(String[] args) {
        /*//处理输入
        Scanner in=new Scanner(System.in);
        int col = in.nextInt();
        int row = in.nextInt();
        int[][] matrix = new int[row][col];
        int max = Integer.MIN_VALUE;
        //初始化岛屿
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                matrix[i][j] = in.nextInt();
            }
        }*/

        int col = 5;
        int row = 5;
        String input = "0 1 1 0 0\t\n0 1 1 0 0\t\n0 0 0 0 0\t\n0 0 1 2 3\t\n0 0 1 3 9";
        int[][] matrix = Arrays.stream(input.split("\t\n"))
                .map(str -> Arrays.stream(str.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        System.out.println(getResult(row, col, matrix));
    }

    public static int area = 0;
    // 上下左右偏移量
    final static int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    private static int getResult(int row, int col, int[][] matrix) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] > 0) {
                    area = 0;
                    //求当前点所属岛屿的大小
                    dfs(matrix, i, j);
                    max = Math.max(area, max);
                }
            }
        }

        return max;
    }

    /**
     * DFS
     *
     * @param matrix
     * @param i
     * @param j
     * @return
     */
    public static void dfs(int[][] matrix, int i, int j) {
        int row = matrix.length;
        int col = matrix[0].length;

        area += matrix[i][j];
        matrix[i][j] = 0;
        for (int[] offset : offsets) {
            int newI = i + offset[0];
            int newJ = j + offset[1];
            if (newI < 0 || newI >= row || newJ < 0 || newJ >= col || matrix[newI][newJ] == 0) {
                continue;
            }
            //上下左右判断是否为1
            dfs(matrix, newI, newJ);
        }
    }
}